package JZ_Offer.dataStructure.tree;

import base.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 二叉搜索树与双向链表
 * <p>
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 *
 * @Author piper
 * @Date 2019/12/24 1:46 下午
 */
public class JZ36_二叉搜索树与双向链表 {

    private static TreeNode Convert(TreeNode pRootOfTree) {
        // 1 中序遍历树 得到链表
        inOrder(pRootOfTree);

        // 2 修改链表节点指针
        TreeNode head = queue.poll(), pre = null;
        for (TreeNode cur = head; cur != null; cur = queue.poll()) {
            cur.left = pre;
            if (pre != null) {
                pre.right = cur;
            }
            pre = cur;
        }

        return head;
    }

    private static Queue<TreeNode> queue = new ArrayDeque<>();

    private static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder((root.left));
        queue.add(root);
        inOrder(root.right);
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        d.left = b;
        d.right = f;
        b.left = a;
        b.right = c;
        f.left = e;

        TreeNode treeNode = Convert(d);
        while (treeNode != null) {
            System.out.println(treeNode.val);
            treeNode = treeNode.right;
        }
    }
}
